package linklist;

import org.junit.Test;

import java.util.List;
import java.util.Stack;

public class LeetCode_206 {

    private class ListNode {
       int val;
       ListNode next;
       ListNode() {}
       ListNode(int val) { this.val = val; }
       ListNode(int val, ListNode next) { this.val = val; this.next = next; }
   }

    public ListNode reverseList(ListNode head) {

        return solution_2(head);
    }
    @Test
    public void test() {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5,null)))));
        head =solution_2(head);
        System.out.println(printLinkList(head));
    }


    //方法1：直接将值放入栈中，在创建链表即可
    public  ListNode solution_1(ListNode head) {
        //将值放入栈中
        Stack<Integer> stack = new Stack<>();
        while (head != null) {
            stack.push(head.val);
            head = head.next;
        }
        ListNode result = new ListNode();
        ListNode temp = result;
        //从栈中取值，并创建链表
        while (!stack.isEmpty()) {
            temp.next = new ListNode(stack.pop());
            temp=temp.next;
        }
        temp.next=null;
        return result.next;
    }

    //方法2：利用双指针
    public  ListNode solution_2(ListNode head) {

        if (head==null||head.next==null){
            return head;
        }

        //定义快慢指针
        ListNode fast = head.next,slow=head;
        slow.next=null;
        while (fast!=null){
            ListNode temp =fast.next;
            fast.next=slow;
            slow=fast;
            fast=temp;
        }
        return slow;

    }




    public static String printLinkList(ListNode head) {
        String res = "";
        while (head!=null) {
            res += head.val + "->";
            head=head.next;
        }
        return res;
    }


}
